import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode18_SumOfFourNums {
    public static void main(String[] args) {
        System.out.println(fourSum(new int[]{1,0,-1,0,-2,2}, 0));
    }
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        int p1 = 0;
        int len = nums.length;
        while (p1 < len - 3) {
            int p2 = p1 + 1;
            while (p2 < len - 2) {
                int left = p2 + 1;
                int right = len - 1;
                while (left < right) {
                    if (nums[p1] + nums[p2] + nums[left] + nums[right] == target) {
                        System.out.println(nums[p1] + " " + nums[p2] + " " + nums[left] + " " + nums[right]);
                        list.add(new ArrayList<Integer>(Arrays.asList(nums[p1], nums[p2], nums[left], nums[right])));
                        int numLeft = nums[left++];
                        int numRight = nums[right--];
                        while (nums[left] == numLeft && left < right) {
                            left++;
                        }
                        while (nums[right] == numRight && left < right) {
                            right--;
                        }
                    } else if (nums[p1] + nums[p2] + nums[left] + nums[right] < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
                int numP2 = nums[p2++];
                while (p2 < len - 2 && nums[p2] == numP2) {
                    p2++;
                }
            }
            int numP1 = nums[p1++];
            while (p1 < len - 3 && nums[p1] == numP1) {
                p1++;
            }
        }

        return list;
    }

//    public List<List<Integer>> fourSum(int[] nums, int target) {
//        Long[] arr = new Long[nums.length];
//        int count = 0;
//        for (int i : nums) {
//            Long num = Long.valueOf(i);
//            arr[count++] = num;
//        }
//        return fourSum(arr, Long.valueOf(target));
//    }
//    public List<List<Integer>> fourSum(Long[] nums, Long target) {
//        List<List<Integer>> list = new ArrayList<>();
//        Arrays.sort(nums);
//        int p1 = 0;
//        int len = nums.length;
//        while (p1 < len - 3) {
//            int p2 = p1 + 1;
//            while (p2 < len - 2) {
//                int left = p2 + 1;
//                int right = len - 1;
//                while (left < right) {
//                    if (nums[p1] + nums[p2] == target - nums[left] - nums[right]) {
//                        list.add(new ArrayList<Integer>(Arrays.asList(Math.toIntExact(nums[p1]), Integer.valueOf(Math.toIntExact(nums[p2])), Math.toIntExact(nums[left]), Integer.valueOf(Math.toIntExact(nums[right])))));
//                        Long numLeft = nums[left++];
//                        Long numRight = nums[right--];
//                        while (nums[left] == numLeft && left < right) {
//                            left++;
//                        }
//                        while (nums[right] == numRight && left < right) {
//                            right--;
//                        }
//                    } else if (nums[p1] + nums[p2] < target - nums[left] - nums[right]) {
//                        left++;
//                    } else {
//                        right--;
//                    }
//                }
//                Long numP2 = nums[p2++];
//                while (p2 < len - 2 && nums[p2] == numP2) {
//                    p2++;
//                }
//            }
//            Long numP1 = nums[p1++];
//            while (p1 < len - 3 && nums[p1] == numP1) {
//                p1++;
//            }
//        }
//
//        return list;
//    }
}
